package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-23 11:11
 */
public class canJump55 {

    /**55. 跳跃游戏
     * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
     * 贪心，每一步都计算一下从当前位置最远能够跳到哪里，然后和一个全局最优的最远位置 farthest 做对比，通过每一步的最优解，更新全局最优解，
     * */
    public boolean canJump(int[] nums) {
        int n=nums.length;
        if (n<=1) return true;
        int farthest=0;
        for (int i = 0; i < n-1; i++) {
            farthest=Math.max(farthest,i+nums[i]);
            if (farthest<=i){
                //可能碰到0，卡住了
                return false;
            }
        }
        return farthest>=n-1;
    }
    /**45. 跳跃游戏 II
     *给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     * i 和 end 标记了可以选择的跳跃步数，farthest 标记了所有选择 [i..end] 中能够跳到的最远距离，jumps 记录了跳跃次数。
     * */
    public int jump(int[] nums) {
        int n=nums.length;
        int end=0,farthest=0;
        int jumps=0;
        for (int i = 0; i < n-1; i++) {
            farthest=Math.max(nums[i]+i,farthest);
            if (end==i){
                //遍历到了[i,end]中的位置能够跳到的最远距离，就决定跳到[i,end]中能使得下一步跳到farthest的位置，然后继续遍历，最远这个位置变为end
                jumps++;
                end=farthest;
            }
        }
        return jumps;
    }
}
